﻿#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

//class A
//{
//public:
//	A(int a) :_a1(a)
//	{
//		cout << "A(int a)" << endl;
//	}
//
//	A(const A& aa) :_a1(aa._a1)
//	{
//		cout<<"A(const A& aa)"<<endl;
//	}
//
//	static void geta3()
//	{
//		cout << a3;
//	}
//
//private:
//	int _a1;
//	int _a2;
//	static int a3;
//};
//int A::a3 = 3333;
//int main()
//{
//	A aa1(1);
//	A a2 = 6;
//	A a3(a2);
//	A::geta3();
//	return 0;
//}

//
//class Time
//{
//	friend class Date;   // 声明日期类为时间类的友元类，则在日期类中就直接访问Time类
//
//public:
//	Time(int hour = 0, int minute = 0, int second = 0)
//		: _hour(hour)
//		, _minute(minute)
//		, _second(second)
//	{}
//
//
//	int _hour;
//	int _minute;
//	int _second;
//};
//class Date
//{
//public:
//	Date(int year = 1900, int month = 1, int day = 1)
//		: _year(year)
//		, _month(month)
//		, _day(day)
//	{}
//
//	void SetTimeOfDate(int hour, int minute, int second)
//	{
//		// 直接访问时间类私有的成员变量
//		_time._hour = hour;
//		_time._minute = minute;
//		_time._second = second;
//	}
//
//
//	int _year;
//	int _month;
//	int _day;
//	Time _time;
//};
//int main()
//
//{
//	Date a;
//	cout << Date()._time._hour;
//}


//template<class T,class F>
//T Add(const T& a,const F& b)
//{
//	return a + b;
//}
//int main()
//{
//	int a1 = 10, a2 = 20;
//	double d1 = 10.11, d2 = 20.22;
//
//	cout << Add(a1, a2) << endl;
//	cout << Add(d1, d2) << endl;
//	cout << Add(a1, d1) << endl;
//
//	return 0;
//}


//int main()
//{
//
//	string s1("hello");
//	string s2(s1, 2, 2);
//	string s3(s1, 2);
//	string s5("hehehe", 2);
//	cout << s1 << " " << s2 << " " << s3 << " " << s5 << endl;
//	s3 += s2;
//	cout << s3 << endl;
//	string s4(s3);
//	cout << s4 << endl;
//
//	s4.insert(0, "88");
//	cout << s4 << endl;
//
//	s4.insert(2, 3,'9');
//	cout << s4 << endl;
//
//	cout << endl;
//	int count[26] = { 0 };
//	for (auto ch : s1)
//	{
//		count[ch - 'a']++;
//	}
//	for (int i = 0; i < s1.size(); i++)
//	{
//		if (count[s1[i] - 'a'] == 2)
//		{
//			count[s1[i] - 'a']--;
//			cout << s1[i] << endl;
//			
//		}
//	}
//	string s6("The function of the heart is to pump blood through the body");
//	size_t pos = s6.find(' ');
//	int n = 0;
//	for (auto ch : s6)
//	{
//		if (ch == ' ')
//			++n;
//	}
//	s6.reserve(s6.size() + n * 2);
//	while (pos != string::npos)
//	{
//		s6.replace(pos, 1, "~~~");
//		pos = s6.find(' ',pos+3);
//	}
//	cout << s6 << endl;
//	
//	
//	
//	return 0;
//}
//#include <typeinfo>
//int main()
//{
//	string s("1234");
//	std::type_info const& ti = typeid(stoi(s));
//	cout <<ti.name() << endl;
//	return 0;
//}


//int main()
//{
//	vector<int> v{ 1,2,34,5 };
//	for (auto a : v)
//	{
//		cout << a << ' ';
//	}
//	cout << endl;
//	
//	for (size_t i = 0; i < v.size(); ++i)
//	{
//		cout << v[i] << " ";
//	}
//	cout << endl;
//
//	auto it = v.begin();
//	while (it != v.end())
//	{
//		cout << *it++ << " ";
//	
//	}
//	vector<char> v2{ 's' };
//	v2.resize(9);
//	cout << endl;
//
//	for (size_t i = 0; i < v2.size(); ++i)
//	{
//		cout << v2[i] << " ";
//	}
//	cout << endl;
//
//	vector<int> t;
//	size_t sz = t.capacity();
//	for (int i = 0; i < 100; ++i)
//	{
//		t.push_back(i);
//		if (t.capacity() != sz)
//		{
//			sz = t.capacity();
//			cout << "capacity changed: " << sz << endl;
//		}
//	}
//
//
//
//
//	return 0;
//}


//#include <iostream>
//#include <vector>

//#include "vector.h"
//int main() {
//    // 创建一个空的 vector
//    std::vector<int> vec;
//
//    // 第一部分: 使用 assign 分配 5 个元素，并且每个元素初始化为 0
//    vec.assign(5, 0);  // 使用值 0 初始化 5 个元素
//
//    // 输出向量的内容
//    std::cout << "After assigning five zeros: ";
//    for (int i : vec)
//    {
//        std::cout << i << " ";
//    }
//    std::cout << std::endl;
//
//    // 第二部分: 使用 arr 数组的地址作为迭代器，来重新初始化 vec
//    int arr[] = { 1, 2, 3, 4, 5 };
//
//    // 使用 arr 的内容重新初始化 vec
//    vec.assign(arr, arr + sizeof(arr) / sizeof(arr[0]));
//
//    // 输出向量的内容
//    std::cout << "After assigning from array: ";
//    for (int i : vec)
//    {
//        std::cout << i << " ";
//    }
//    std::cout << std::endl;
//
//    return 0;
//}
////#include "vector.h"
////int main()
////{
////	vector<int> v1(10, 5);
////	hanv::test5();
////}



//#include <list>
//int main()
//{
//
//	int array[] = { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 };
//
//	int n = sizeof(array) / sizeof(int);
//
//	list<int> mylist(array, array + n);
//
//	auto it = mylist.begin();
//
//	while (it != mylist.end())
//
//	{
//
//		if (*it != 0)
//
//			cout << *it << " ";
//
//		else
//
//			it = mylist.erase(it);
//
//		++it;
//
//	}
//
//	return 0;

//}

//#include <iostream>
//#include <queue>
//#include <vector>
//
//using namespace std;
//
//int main() {
//    // 构造一个空的优先级队列
//    priority_queue<int> pq;
//
//    // 检测优先级队列是否为空
//    if (pq.empty()) {
//        cout << "优先级队列为空" << endl;
//    }
//    else {
//        cout << "优先级队列不为空" << endl;
//    }
//
//    // 使用迭代器范围构造优先级队列
//    vector<int> nums = { 3, 1, 4, 1, 5, 9 };
//    priority_queue<int, vector<int>, greater<int>> pq2(nums.begin(), nums.end());
//
//    // 输出堆顶元素
//    cout << "堆顶元素为: " << pq2.top() << endl;
//
//    // 在优先级队列中插入元素
//    pq2.push(2);
//    pq2.push(7);
//
//    // 输出堆顶元素
//    cout << "堆顶元素为: " << pq2.top() << endl;
//
//    // 删除堆顶元素
//    pq2.pop();
//    pq2.pop();
//    // 输出堆顶元素
//    cout << "堆顶元素为: " << pq2.top() << endl;
//
//    return 0;
//}


//#include "priority_queue.h"
//int main()
//{
//	hanpq::test_priority_queue();
//	return 0;
//}

//class Solution
//{
//public:
//	bool IspPopOrder(vector<int>&pushV, vector<int>&popV)
//	{
//		stack<int> st;
//		size_t i = 0, j = 0;
//		while (i<pushV.size())
//		{
//			st.push(pushV[i++]);
//			while(!st.empty()&&popV[j] == st.top())
//			{
//				st.pop();
//				j++;
//			}
//		}
//		return j == pushV.size();
//	}
//};
//
//template<class T1,class T2>
//class Date
//{
//public:
//	Data() { std::cout << "Data<T1, T2>" << std::endl; }
//private:
//	T1 _d1;
//	T2 _d2;
//};
//
//template<>
//class Date<int,char>
//{
//public:
//	Date() { std::cout << "Data<int,char>" << std::endl; }
//private:
//	int _d1;
//	char _d2;
//};
//
//template<class T1>
//class Date<T1, int>
//{
//public:
//
//};
//
//#include <iostream>
//
//// 示例容器 MyContainer
//template<typename T>
//class MyContainer {
//public:
//	// 假设 MyContainer 具有成员函数 begin() 返回迭代器
//	class iterator {
//	public:
//		iterator(T* ptr) : ptr(ptr) {}
//		T& operator*() const { return *ptr; }
//		iterator& operator++() { ++ptr; return *this; }
//		bool operator!=(const iterator& other) const { return ptr != other.ptr; }
//	private:
//		T* ptr;
//	};
//
//	iterator begin() const { return iterator(data); }
//private:
//	T data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//};
//
//template<typename Container>
//void printFirstElement(const Container& container) {
//	typename Container::iterator it = container.begin(); // 编译错误
//	std::cout << "First element: " << *it << std::endl;
//}


//#include <iostream>
//using namespace std;
//
//class A {
//public:
//	A(const char* s) { cout << s << endl; }
//	~A() {}
//};
//
//class B : virtual public A {
//public:
//	B(const char* s1, const char* s2) : A(s1) {
//		cout << s2 << endl;
//	}
//};
//
//class C : virtual public A {
//public:
//	C(const char* s1, const char* s2) : A(s1) {
//		cout << s2 << endl;
//	}
//};
//
//class D : public B, public C {
//public:
//	D(const char* s1, const char* s2, const char* s3, const char* s4) : C(s1, s2), B(s1, s3), A(s1) {
//		cout << s4 << endl;
//	}
//};
//
//int main() {
//	D* p = new D("class A", "class B", "class C", "class D");
//	delete p;
//	return 0;
//}


//class Person
//{
//public:
//	virtual void BuyTicket() { cout << "full price" << endl; }
//};
//
//class Student :public Person
//{
//public:
//	virtual void BuyTicket() { cout << "half price" << endl; }
//};
//
//void Func(Person& p)
//{
//	p.BuyTicket();
//}
//
//int main()
//{
//	Person p;
//	Student s;
//	Func(p);
//	Func(s);
//}
//class Base
//{
//public:
//	virtual void Func1()
//	{
//		cout << "Func1()" << endl;
//	}
//private:
//	int _b = 1;
//};
//
//int main()
//{
//	Base b;
//	return 0;
//}


//class Base
//{
//public:
//	virtual void Func1()
//	{
//		cout << "Base::Func1()" << endl;
//	}
//	virtual void Func2()
//	{
//		cout << "Base::Func2()" << endl;
//	}
//	void Func3()
//	{
//		cout << "Base::Func3()" << endl;
//	}
//private:
//	int _b = 1;
//};
//class Derive : public Base
//{
//public:
//	virtual void Func1()
//	{
//		cout << "Derive::Func1()" << endl;
//	}
//private:
//	int _d = 2;
//};
//int main()
//{
//	Base b;
//	derive d;
//	return 0;
//}

//class Base
//{
//public:
//	Base():_b(10)
//	{
//		++_b;
//	}
//
//	virtual void Func1()
//	{
//		cout << "Base::Func1()" << endl;
//	}
//
//	virtual void Func2()
//	{
//		cout << "Base::Func2()" << endl;
//	}
//
//	void Func3()
//	{
//		cout << "Base::Func3()" << endl;
//	}
//
//private:
//	int _b = 1;
//};
//
//class Derive : public Base
//{
//public:
//	virtual void Func1()
//	{
//		cout << "Derive::Func()" << endl;
//	}
//
//	virtual void Func4()
//	{
//		cout << "Derive::Func4()" << endl;
//	}
//private:
//	int _d = 2;
//};
//
//typedef void(*VF_PTR)();
//void PrintVFTable(VF_PTR table[])
//{
//	for (int i = 0; table[i] != nullptr; ++i)
//	{
//		printf("[%d]:%p->", i, table[i]);
//		VF_PTR f = table[i];
//		f();
//	}
//}


//#include <iostream>
//
//void incrementThroughDoublePointer(int** ptr)
//{
//    // 假设 *ptr 指向一个 int 类型的指针
//    (*ptr)++;
//    // 输出通过二级指针间接访问的值
//    std::cout << "Value through double pointer: " << **ptr << std::endl;
//}
//
//int main()
//{
//    int x = 5; // 声明一个 int 类型的变量
//    int* ptr = &x; // ptr 指向 x 的地址
//    int** ptr2 = &ptr; // ptr2 是一个二级指针，指向 ptr 的地址
//
//    std::cout << "Initial value of x: " << x << std::endl;
//    std::cout << "Address of x: " << &x << std::endl;
//    std::cout << "ptr points to: " << ptr << std::endl;
//    std::cout << "ptr2 points to: " << ptr2 << std::endl;
//
//    incrementThroughDoublePointer(ptr2); // 通过二级指针修改 x 的值
//
//    std::cout << "Final value of x: " << x << std::endl;
//    std::cout << "ptr points to: " << ptr << std::endl;
//    std::cout << "ptr2 points to: " << ptr2 << std::endl;
//
//    return 0;
//}

//#include "BSTree.h"
//
//int main()
//{
//	hanB::BSTree<int> t;
//	int n = rand() % 100;
//	for (int i = 0; i < 10; ++i)
//	{
//		t.Insert(n);
//		n = rand() % 15;
//	}
//	t.InOrder();
//	cout << t.FindR(2) << endl <<t.Find(4)  << endl;
//	return 0;
//}


//#include <iostream>
//#include <queue>
//#include <vector>
//
//using namespace std;
//
//int main() {
//	// 构造一个空的优先级队列
//	priority_queue<int> pq;
//
//	// 检测优先级队列是否为空
//	if (pq.empty()) {
//		cout << " 优先级队列为空" << endl;
//	}
//	else {
//		cout << "优先级队列不为空" << endl;
//	}
//
//	// 使用迭代器范围构造优先级队列
//	vector<int> nums = { 3, 1, 4, 1, 5, 9 };
//	priority_queue<int, vector<int>, greater<int>> pq2(nums.begin(), nums.end());
//
//	// 输出堆顶元素
//	cout << "堆顶元素为: " << pq2.top() << endl;
//
//	// 在优先级队列中插入元素
//	pq2.push(2);
//	pq2.push(7);
//
//	// 输出堆顶元素
//	cout << "堆顶元素为: " << pq2.top() << endl;
//
//	// 删除堆顶元素
//	pq2.pop();
//	pq2.pop();
//
//	// 输出堆顶元素
//	cout << "堆顶元素为: " << pq2.top() << endl;
//
//	return 0;
//}


//#include <set>
//#include <map>
//int main()
//{
//	set<int> s{ 1,3,4,1,2,7,8 };
//	auto it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it++ << endl;		
//	}
//	cout << "1 take up: " << s.count(1) << endl;
//
//	map<int, string> m{ {1,"ssp"},{2,"sp"},{3,"p"} };
//	cout << m[2] << endl;
//	m[2] = "test";
//	cout << m[2] << endl;
//}


//#include <algorithm>
//#include <vector>
//#include <iostream>
//
//bool compareDesc(int a, int b) {
//    return a > b; // 返回 a 是否应该排在 b 前面
//}
//
//int main() {
//    std::vector<int> vec = { 4, 2, 5, 1, 3 };
//
//    // 使用自定义比较函数
//    std::sort(vec.begin(), vec.end(), compareDesc);
//    //std::sort(vec.begin(), vec.end());
//    // 输出排序后的向量
//    for (int num : vec) {
//        std::cout << num << " ";
//    }
//    // 输出应该是 1 2 3 4 5
//    return 0;
//}

//#include "AVLTree.h"
//void Test_AVLTree1()
//{
//	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//	AVLTree<int, int> t1;
//	for (auto e : a)
//	{
//		//可以使用这种方式帮助打断点查找错误
//		/*	if (e == 14)
//			{
//			int x = 0;
//			}*/
//
//		t1.Insert(make_pair(e, e));
//		cout << e << "插入：" << t1.IsBalance() << endl;
//	}
//
//	t1.InOrder();
//	cout << t1.IsBalance() << endl;
//}
//int main()
//{
//	Test_AVLTree1();
//}


//#include <unordered_map>
//#include <unordered_set>
//
//int main()
//{
//	unordered_map<int, string> map;
//	bool isempty = map.empty();
//	cout << "empty? -> " << isempty << endl;
//
//	map[1] = "one";
//	map[2] = "two";
//	
//	isempty = map.empty();
//	cout << "empty? -> " << isempty << endl;
//	
//	cout << "size: " << map.size() << endl;
//	for (auto a : map)
//	{
//		cout << a.first << " " << a.second << endl;
//	}
//
//	unordered_map<int,string> map2{ {1, "apple"}, {2, "banana"}, {3, "orange"} };
//	auto it = map.begin();
//	while (it != map.end())
//	{
//		cout << "key: " << it->first;
//	}
//}


//#include "HashTable.h"
//#include <unordered_map>
//int main()
//{
//	OpenAddress::test();
//	return 0;
//}